package leetcode.code1125;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	int[] peoples;
	int size;

	public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
		Map<String, Integer> map = new HashMap<>();
		int len = req_skills.length;
		for (int i = 0; i < len; i++) {
			map.put(req_skills[i], i);
		}
		int skill = (1 << len) - 1;
		size = people.size();
		peoples = new int[size];
		for (int i = 0; i < size; i++) {
			int cur = 0;
			for (String str : people.get(i)) {
				cur |= 1 << map.get(str);
			}
			peoples[i] = cur;
		}
		Map<Integer, Long> dp = new HashMap<>();
		long ans = f(skill, dp);
		int p = Long.bitCount(ans);
		int[] ret = new int[p];
		for (int i = 0, j = 0; i < size; i++) {
			if (((ans >> i) & 1) == 1) {
				ret[j++] = i;
			}
		}
		return ret;
	}

	private long f(int skill, Map<Integer, Long> dp) {
		if (skill == 0) {
			return 0;
		}
		if (dp.containsKey(skill)) {
			return dp.get(skill);
		}
		long ans = (1 << 63) - 1;
		for (int i = 0; i < size; i++) {
			int add = skill & peoples[i];
			if (add != 0) {
				long cur = (1l << i) | f(skill ^ add, dp);
				if (Long.bitCount(cur) < Long.bitCount(ans)) {
					ans = cur;
				}
			}
		}
		dp.put(skill, ans);
		return ans;
	}

	@Override
	public void debug4() {
		H.print(this.smallestSufficientTeam(
				H.str2array2("[\"mwobudvo\",\"goczubcwnfze\",\"yspbsez\",\"pf\",\"ey\",\"hkq\"]"), H.str2intlist2(
						"[[],[\"mwobudvo\"],[\"hkq\"],[\"pf\"],[\"pf\"],[\"mwobudvo\",\"pf\"],[],[\"yspbsez\"],[],[\"hkq\"],[],[],[\"goczubcwnfze\",\"pf\",\"hkq\"],[\"goczubcwnfze\"],[\"hkq\"],[\"mwobudvo\"],[],[\"mwobudvo\",\"pf\"],[\"pf\",\"ey\"],[\"mwobudvo\"],[\"hkq\"],[],[\"pf\"],[\"mwobudvo\",\"yspbsez\"],[\"mwobudvo\",\"goczubcwnfze\"],[\"goczubcwnfze\",\"pf\"],[\"goczubcwnfze\"],[\"goczubcwnfze\"],[\"mwobudvo\"],[\"mwobudvo\",\"goczubcwnfze\"],[],[\"goczubcwnfze\"],[],[\"goczubcwnfze\"],[\"mwobudvo\"],[],[\"hkq\"],[\"yspbsez\"],[\"mwobudvo\"],[\"goczubcwnfze\",\"ey\"]]")));
//		H.print(this.smallestSufficientTeam(
//				H.str2array2("[\"mwobudvo\",\"goczubcwnfze\",\"yspbsez\",\"pf\",\"ey\",\"hkq\"]"), H.str2intlist2(
//						"[[],[\"mwobudvo\"],[\"hkq\"],[\"pf\"],[\"pf\"],[\"mwobudvo\",\"pf\"],[],[\"yspbsez\"],[],[\"hkq\"],[],[],[\"goczubcwnfze\",\"pf\",\"hkq\"],[\"goczubcwnfze\"],[\"hkq\"],[\"mwobudvo\"],[],[\"mwobudvo\",\"pf\"],[\"pf\",\"ey\"],[\"mwobudvo\"],[\"hkq\"],[],[\"pf\"],[\"mwobudvo\",\"yspbsez\"],[\"mwobudvo\",\"goczubcwnfze\"],[\"goczubcwnfze\",\"pf\"],[\"goczubcwnfze\"],[\"goczubcwnfze\"],[\"mwobudvo\"],[\"mwobudvo\",\"goczubcwnfze\"],[],[\"goczubcwnfze\"],[],[\"goczubcwnfze\"],[\"mwobudvo\"],[],[\"hkq\"],[\"yspbsez\"],[\"mwobudvo\"],[\"goczubcwnfze\",\"ey\"]]")));
//		H.print(this.smallestSufficientTeam(H.str2array2("[\"java\",\"nodejs\",\"reactjs\"]"),
//				H.str2intlist2("[[\"java\"],[\"nodejs\"],[\"nodejs\",\"reactjs\"]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
